#include<iostream>
using namespace std;
long long q[1000040];
long long q1[1000040];
long long a[1000050];
long long ans1[1000050];
long long ans2[1000050];
long long ans[1000050];
int main(){
    int n,zs;
    cin>>n>>zs;
   
    
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int j=1;j<=zs;j++){
        int x, y;
        cin>>x>>y;
        int k=y-x+1;
    int h=0,t=0;
    int h1=0,t1=0;
         for(int i=x;i<=y;i++){
            while(h<t&&a[i]>a[q[t-1]])t--;
        t++;
        q[t-1]=i;
        while(q[h]+k<=i&&h<t)h++;
        if(i>=k){
            ans1[j]=a[q[h]];
        }
        while(h1<t1&&a[i]<a[q1[t1-1]])t1--;
        t1++;
        q1[t1-1]=i;
        while(q1[h1]+k<=i&&h1<t1)h1++;
        if(i>=k){
            ans2[j]=a[q1[h1]];
        }
         } 
         ans[j]=ans1[j]-ans2[j];
    }
    for(int i=1;i<=zs;i++)cout<<ans[i]<<endl;
    return 0;
}